//2903.找出满足差值条件的下标I
//https://leetcode.cn/problems/find-indices-with-index-and-value-difference-i
class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        int n = nums.size();
        int maxi = 0,mini = 0; //维护前缀中最大和最小值
        //i~indexDifference范围内的数不能选 不符合要求
        for(int i = indexDifference;i<n;++i)
        {
            //求当前符合要求的数下标
            //例如 5 1 4 1
            //     k  i
            //此时可选的数是满足indexDifference的 且k前面的所有数都是可选的
            //只需要维护k前面最大的和最小的数即可
            int k = i-indexDifference;
            if(nums[maxi] < nums[k]) maxi = k;
            else if(nums[mini] > nums[k]) mini = k;

            if(nums[maxi]-nums[i] >= valueDifference) return {maxi,i};
            if(nums[i]-nums[mini] >= valueDifference) return {mini,i};
        }
        return {-1,-1};
    }
};
